package interview.i_001_algorithm;

import java.util.Arrays;

/**
 * 归并排序，一种稳定(相等的元素排序后是否依然保持原顺序)的排序
 * 时间复杂度：无论是在最好情况下还是在最坏情况下均是O(nlgn)
 * 空间复杂度：O(n)
 */
public class T002_MergeSort {
    static int[] assist;

    public static void main(String[] args) {
        int[] array = new int[]{2, 4, 11, 9, 4, 9, 12, 5, 3};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    static boolean less(int a, int b) {
        return a < b;
    }

    static void exch(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    static void sort(int[] array) {
        assist = new int[array.length];
        sort(array, 0, array.length - 1);
    }

    static void sort(int[] array, int lo, int hi) { // 递归拆分合并
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(array, lo, mid);
        sort(array, mid + 1, hi);
        merge(array, lo, mid, hi);
    }

    static void merge(int[] array, int lo, int mid, int hi) {
        // 三指针路线：k(lo) --> hi，i --> mid，j(mid+1) --> hi
        int k = lo, i = lo, j = mid + 1;
        while (i <= mid && j <= hi) {  // 把较小的数先移到新数组中
            if (less(array[i], array[j])) {
                assist[k++] = array[i++];
            } else {
                assist[k++] = array[j++];
            }
        }
        while (i <= mid) { // 把左边剩余的数移入数组
            assist[k++] = array[i++];
        }
        while (j <= hi) { // 把右边边剩余的数移入数组
            assist[k++] = array[j++];
        }

        // for (int l = lo; l <= hi; l++) { // 拷贝到原数组中
        //     array[l] = assist[l];
        // }
        if (hi - lo >= 0) {
            System.arraycopy(assist, lo, array, lo, hi - lo + 1);
        }
    }
}
